{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Probability of a Two Boxes Having The Same Number of Distinct Balls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming #backtracking #combinatorics #probability-and-statistics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划 #回溯 #组合数学 #概率与统计"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getProbability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个盒子中球的颜色数相同的概率"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>桌面上有 <code>2n</code> 个颜色不完全相同的球，球上的颜色共有 <code>k</code> 种。给你一个大小为 <code>k</code> 的整数数组 <code>balls</code> ，其中 <code>balls[i]</code> 是颜色为&nbsp;<code>i</code> 的球的数量。</p>\n",
    "\n",
    "<p>所有的球都已经 <strong>随机打乱顺序</strong> ，前 <code>n</code> 个球放入第一个盒子，后 <code>n</code> 个球放入另一个盒子（请认真阅读示例 2 的解释部分）。</p>\n",
    "\n",
    "<p><strong>注意：</strong>这两个盒子是不同的。例如，两个球颜色分别为 <code>a</code> 和 <code>b</code>，盒子分别为 <code>[]</code> 和 <code>()</code>，那么 <code>[a] (b)</code> 和 <code>[b] (a)</code> 这两种分配方式是不同的（请认真阅读示例的解释部分）。</p>\n",
    "\n",
    "<p>请返回「两个盒子中球的颜色数相同」的情况的概率。答案与真实值误差在 <code>10^-5</code> 以内，则被视为正确答案</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>balls = [1,1]\n",
    "<strong>输出：</strong>1.00000\n",
    "<strong>解释：</strong>球平均分配的方式只有两种：\n",
    "- 颜色为 1 的球放入第一个盒子，颜色为 2 的球放入第二个盒子\n",
    "- 颜色为 2 的球放入第一个盒子，颜色为 1 的球放入第二个盒子\n",
    "这两种分配，两个盒子中球的颜色数都相同。所以概率为 2/2 = 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>balls = [2,1,1]\n",
    "<strong>输出：</strong>0.66667\n",
    "<strong>解释：</strong>球的列表为 [1, 1, 2, 3]\n",
    "随机打乱，得到 12 种等概率的不同打乱方案，每种方案概率为 1/12 ：\n",
    "[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]\n",
    "然后，我们将前两个球放入第一个盒子，后两个球放入第二个盒子。\n",
    "这 12 种可能的随机打乱方式中的 8 种满足「两个盒子中球的颜色数相同」。\n",
    "概率 = 8/12 = 0.66667\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>balls = [1,2,1,2]\n",
    "<strong>输出：</strong>0.60000\n",
    "<strong>解释：</strong>球的列表为 [1, 2, 2, 3, 4, 4]。要想显示所有 180 种随机打乱方案是很难的，但只检查「两个盒子中球的颜色数相同」的 108 种情况是比较容易的。\n",
    "概率 = 108 / 180 = 0.6 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= balls.length &lt;= 8</code></li>\n",
    "\t<li><code>1 &lt;= balls[i] &lt;= 6</code></li>\n",
    "\t<li><code>sum(balls)</code> 是偶数</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [probability-of-a-two-boxes-having-the-same-number-of-distinct-balls](https://leetcode.cn/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [probability-of-a-two-boxes-having-the-same-number-of-distinct-balls](https://leetcode.cn/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1]', '[2,1,1]', '[1,2,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import math\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        n = sum(balls) // 2\n",
    "        k = len(balls)\n",
    "        def combine(x,y):\n",
    "            return math.factorial(x) // (math.factorial(y) * math.factorial(x-y))\n",
    "        def dfs(i,j,z):\n",
    "            if i == k:\n",
    "                return int(j == n and z == 0)\n",
    "            rtn = dfs(i+1,j,z-1) + dfs(i+1,j+balls[i],z+1)\n",
    "            for p in range(1,balls[i]):\n",
    "                rtn += dfs(i+1,j+p,z) * comb(balls[i],p)\n",
    "            return rtn\n",
    "        ans = dfs(0,0,0)\n",
    "        # print(ans,comb(2*n,n))\n",
    "        return ans / comb(2*n,n)\n",
    "\n",
    "        \n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        k=len(balls)\n",
    "        n=0\n",
    "        for i in balls:\n",
    "            n=n+i\n",
    "        n=int (n/2)\n",
    "        hal_ball=[0 for _ in range(k)]\n",
    "        \n",
    "\n",
    "        def c(n,m):\n",
    "           return math.factorial(n)/(math.factorial(m)*math.factorial(n-m))\n",
    "\n",
    "\n",
    "\n",
    "        def dfs(i:int,hal_ball: List[int],cnt:int):\n",
    "            if i==k:\n",
    "                if cnt!=0:\n",
    "                    return 0\n",
    "                x=0\n",
    "                y=0\n",
    "                res=1\n",
    "                for j in range(len(hal_ball)):\n",
    "                    \n",
    "                    if hal_ball[j]==0:\n",
    "                        x=x+1\n",
    "                    elif hal_ball[j]==balls[j]:\n",
    "                        y=y+1\n",
    "                if x==y:\n",
    "                    for j in range(len(hal_ball)):\n",
    "                        res=res*c(balls[j],hal_ball[j])\n",
    "                    return res\n",
    "                else:\n",
    "                    return 0\n",
    "            ans=0\n",
    "            tmp=min(cnt,balls[i])\n",
    "\n",
    "            for j in range(tmp+1):\n",
    "                hal_ball[i]=j\n",
    "                ans+=dfs(i+1,hal_ball,cnt-j)\n",
    "            return ans\n",
    "\n",
    "        return dfs(0,hal_ball,n)/c(2*n,n)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        k = len(balls)\n",
    "        n = sum(balls) // 2\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, re, c):\n",
    "            if idx == k:\n",
    "                return re == 0 and c == 0\n",
    "            \n",
    "            res = 0\n",
    "            for i in range(min(balls[idx], re) + 1):\n",
    "                t = c\n",
    "                if i == 0:\n",
    "                    t -= 1\n",
    "                elif i == balls[idx]:\n",
    "                    t += 1\n",
    "                res += dfs(idx + 1, re - i, t) * comb(balls[idx], i)\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0, n, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans / comb(2 * n, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def combine(x, y):#组合数\n",
    "            return math.factorial(x) // math.factorial(y) // math.factorial(x - y)\n",
    "        s = sum(balls)#球总数\n",
    "        l = len(balls)#颜色总数\n",
    "        #@lru_cache(None)\n",
    "        def dfs(i, c, t):\n",
    "            if i == l:#如果颜色选完了\n",
    "                return int(t == 0 and c == s // 2) #选了1/2的球数量且颜色无变化\n",
    "            res = dfs(i + 1, c, t + 1) + dfs(i + 1, c + balls[i], t - 1)#不选和全选组合数都为1，直接相加即可，需要更新颜色变化\n",
    "            for j in range(1, balls[i]):#其他情况，颜色无变化\n",
    "                res += dfs(i + 1, c + j, t) * combine(balls[i], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / combine(s, s // 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        s=sum(balls)\n",
    "        color=len(balls)\n",
    "\n",
    "        total=comb(s,s//2)\n",
    "        res=0\n",
    "        def dfs(i,b,t):\n",
    "            if i==color:\n",
    "                if t == 0 and b == s // 2:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            res=dfs(i+1,b,t-1)+dfs(i+1,b+balls[i],t+1)\n",
    "            for j in range(1,balls[i]):\n",
    "                res+=dfs(i+1,b+j,t)*comb(balls[i],j)\n",
    "            return res\n",
    "        res=dfs(0,0,0)\n",
    "        return res/total\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "\n",
    "\n",
    "        sum_balls = sum(balls)\n",
    "        color_num = len(balls)\n",
    "\n",
    "        def DFS(i, c, t): \n",
    "            # i: color, \n",
    "            # c: # of balls, \n",
    "            # t: even index \n",
    "\n",
    "            if i== color_num:\n",
    "                return int(t==0 and c==(sum_balls//2) )\n",
    "            if c>(sum_balls//2):\n",
    "                return 0 \n",
    "\n",
    "            res = DFS(i+1,c,t-1)+DFS(i+1,c+balls[i],t+1)\n",
    "            for j in range(1,balls[i]):\n",
    "                res += DFS(i+1,c+j,t)*math.comb(balls[i], j)\n",
    "            return res \n",
    "        \n",
    "        res = DFS(0,0,0)\n",
    "        return res/math.comb(sum_balls, sum_balls//2)\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def getRes(lst):\n",
    "            res = 1\n",
    "            for x, y in zip(lst, balls):\n",
    "                res *= comb(y, x)\n",
    "            return res\n",
    "        ans = 0\n",
    "        tmp = 0\n",
    "        def dfs(idx, tmp1, tmp2):\n",
    "            nonlocal ans, tmp\n",
    "            if idx == len(balls):\n",
    "                if sum(tmp1) == sum(tmp2):\n",
    "                    methods = getRes(tmp1)\n",
    "                    if tmp1.count(0) == tmp2.count(0):\n",
    "                        ans += methods\n",
    "                    tmp += methods\n",
    "                return \n",
    "            for i in range(balls[idx]+1):\n",
    "                tmp1.append(i)\n",
    "                tmp2.append(balls[idx]-i)\n",
    "                dfs(idx+1, tmp1, tmp2)\n",
    "                tmp1.pop()\n",
    "                tmp2.pop()\n",
    "        dfs(0, [], [])\n",
    "        return ans / tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        # 计算组合排列个数，长度为total，每种颜色球个数为arr\n",
    "        def compute(total, arr):\n",
    "            res = 1\n",
    "            for num in arr:\n",
    "                res *= math.comb(total, num)\n",
    "                total -= num\n",
    "            return res\n",
    "\n",
    "        # 查看其是否符合条件\n",
    "        def check():\n",
    "            if sum(choose) != n:\n",
    "                return 0\n",
    "            if color1 != color2:\n",
    "                return 0\n",
    "            return compute(n, choose) * compute(n, [balls[i] - choose[i] for i in range(k)])\n",
    "\n",
    "        # 深搜进行数量枚举\n",
    "        def dfs(i):\n",
    "            nonlocal count, color1, color2, pre\n",
    "            # 剪枝\n",
    "            if pre > n:\n",
    "                return\n",
    "            if i == k:\n",
    "                count += check()\n",
    "                return\n",
    "            for j in range(balls[i] + 1):\n",
    "                # 回溯\n",
    "                choose.append(j)\n",
    "                color1 += 1 if j > 0 else 0\n",
    "                color2 += 1 if j < balls[i] else 0\n",
    "                dfs(i + 1)\n",
    "                color1 -= 1 if j > 0 else 0\n",
    "                color2 -= 1 if j < balls[i] else 0\n",
    "                choose.pop()\n",
    "            return\n",
    "\n",
    "        k = len(balls)\n",
    "        total = sum(balls)\n",
    "        n = total // 2\n",
    "        # 颜色数量与组合种数\n",
    "        count = color1 = color2 = 0\n",
    "        choose = []\n",
    "        pre = 0\n",
    "        dfs(0)\n",
    "        return count / compute(total, balls)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def perm(nums: List[int]) -> int:\n",
    "            return factorial(sum(nums)) // prod([factorial(k) for k in nums])\n",
    "        def solve(nums: List[int], i: int) -> int:\n",
    "            if i == n:\n",
    "                if sum(nums) != m: return 0\n",
    "                n1 = nums\n",
    "                n2 = [balls[i] - nums[i] for i in range(n)]\n",
    "                k1 = sum(k != 0 for k in n1)\n",
    "                k2 = sum(k != 0 for k in n2)\n",
    "                return perm(n1) * perm(n2) if k1 == k2 else 0\n",
    "            num = 0\n",
    "            for k in range(balls[i] + 1):\n",
    "                nums[i] = k\n",
    "                num += solve(nums, i + 1)\n",
    "            return num\n",
    "        m = sum(balls) >> 1\n",
    "        n = len(balls)\n",
    "        return solve([0] * n, 0) / perm(balls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def getRes(tmp): \n",
    "            res=1\n",
    "            for (x, y) in zip(tmp, balls):\n",
    "                res*=math.comb(y, x)\n",
    "            return res\n",
    "        ans,tmp=0,0\n",
    "        def dfs(idx, tmp0, tmp1):\n",
    "            nonlocal ans,tmp\n",
    "            if idx==len(balls):\n",
    "                if sum(tmp0)==sum(tmp1):\n",
    "                    methods=getRes(tmp0)\n",
    "                    if tmp0.count(0)==tmp1.count(0):\n",
    "                        ans+=methods\n",
    "                    tmp+=methods\n",
    "            else:\n",
    "                for i in range(balls[idx]+1):\n",
    "                    tmp0.append(balls[idx]-i)\n",
    "                    tmp1.append(i)\n",
    "                    dfs(idx+1, tmp0, tmp1)\n",
    "                    tmp0.pop()\n",
    "                    tmp1.pop()\n",
    "\n",
    "        dfs(0, [], [])\n",
    "        return ans/tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fact(self, n):\n",
    "        ans = 1\n",
    "        for i in range (1, n + 1):\n",
    "            ans *= i\n",
    "        return ans\n",
    "\n",
    "    def get(self, balls):\n",
    "        tot = self.fact(sum(balls))\n",
    "        for b in balls:\n",
    "            if b:\n",
    "                tot /= self.fact(b)\n",
    "        return tot\n",
    "\n",
    "    def dfs(self, u, balls, left, right, ts, ls, rs):\n",
    "        if ls * 2 > ts or rs * 2 > ts: return 0\n",
    "        if u == len(balls):\n",
    "            l = 0\n",
    "            r = 0\n",
    "            for x in left:\n",
    "                if x:\n",
    "                    l += 1\n",
    "            for x in right:\n",
    "                if x:\n",
    "                    r += 1\n",
    "            if l != r: return 0\n",
    "            return self.get(left) * self.get(right)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(balls[u] + 1):\n",
    "            left[u] = i\n",
    "            right[u] = balls[u] - i\n",
    "            res += self.dfs(u + 1, balls, left, right, ts, ls + left[u], rs + right[u])\n",
    "        return res\n",
    "\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        l = [0 for i in range(len(balls))]\n",
    "        r = [0 for i in range(len(balls))]\n",
    "        return self.dfs(0, balls, l, r, sum(balls), 0, 0) / self.get(balls)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def getRes(lst):\n",
    "            res = 1\n",
    "            for x, y in zip(lst, balls):\n",
    "                res *= comb(y, x)\n",
    "            return res\n",
    "        ans = 0\n",
    "        tmp = 0\n",
    "        def dfs(idx, tmp1, tmp2):\n",
    "            nonlocal ans, tmp\n",
    "            if idx == len(balls):\n",
    "                if sum(tmp1) == sum(tmp2):\n",
    "                    methods = getRes(tmp1)\n",
    "                    if tmp1.count(0) == tmp2.count(0):\n",
    "                        ans += methods\n",
    "                    tmp += methods\n",
    "                return \n",
    "            for i in range(balls[idx]+1):\n",
    "                tmp1.append(i)\n",
    "                tmp2.append(balls[idx]-i)\n",
    "                dfs(idx+1, tmp1, tmp2)\n",
    "                tmp1.pop()\n",
    "                tmp2.pop()\n",
    "        dfs(0, [], [])\n",
    "        return ans / tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import comb\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        total = sum(balls)\n",
    "        color = len(balls)\n",
    "        half = total // 2\n",
    "        all_ways = comb(total, half)\n",
    "        \n",
    "        # 计算颜色分配的可能性\n",
    "        def dfs(idx, left, right, color_left, color_right):\n",
    "            if left > half or right > half:\n",
    "                return 0\n",
    "            if idx == color:\n",
    "                if left == right and color_left == color_right:\n",
    "                    return comb(total - left, half - left)\n",
    "                return 0\n",
    "            ways = 0\n",
    "            for i in range(balls[idx] + 1):\n",
    "                ways += dfs(idx + 1, left + i, right + balls[idx] - i, color_left + (i > 0), color_right + (i < balls[idx])) * comb(balls[idx], i)\n",
    "            return ways\n",
    "        \n",
    "        good_ways = dfs(0, 0, 0, 0, 0)\n",
    "        \n",
    "        return good_ways / all_ways\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "\n",
    "        n = len(balls)\n",
    "        s = sum(balls)\n",
    "        @cache\n",
    "        def dfs(idx, cnt, diff):\n",
    "            if idx == n:\n",
    "                return int(diff == 0 and cnt == s // 2)\n",
    "            \n",
    "            res = dfs(idx + 1, cnt, diff - 1) + dfs(idx + 1, cnt + balls[idx], diff + 1)\n",
    "\n",
    "            for j in range(1, balls[idx]):\n",
    "                res += dfs(idx + 1, cnt + j, diff) * comb(balls[idx], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / comb(s, s // 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import comb\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        total = sum(balls)\n",
    "        color = len(balls)\n",
    "        half = total // 2\n",
    "        all_ways = comb(total, half)\n",
    "        \n",
    "        # 计算颜色分配的可能性\n",
    "        def dfs(idx, left, right, color_left, color_right):\n",
    "            if left > half or right > half:\n",
    "                return 0\n",
    "            if idx == color:\n",
    "                if left == right and color_left == color_right:\n",
    "                    return comb(total - left, half - left)\n",
    "                return 0\n",
    "            ways = 0\n",
    "            for i in range(balls[idx] + 1):\n",
    "                ways += dfs(idx + 1, left + i, right + balls[idx] - i, color_left + (i > 0), color_right + (i < balls[idx])) * comb(balls[idx], i)\n",
    "            return ways\n",
    "        \n",
    "        good_ways = dfs(0, 0, 0, 0, 0)\n",
    "        \n",
    "        return good_ways / all_ways"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        n, s = len(balls), sum(balls)\n",
    "        half = s >> 1\n",
    "        @cache\n",
    "        def dfs(index, num, diff):\n",
    "            if index == n:\n",
    "                return int(num == half and diff == 0)\n",
    "            # 这个颜色选择多少进入一个其中一个箱子\n",
    "            # 要么一个不选 要么全部选进其中一个箱子 这会导致颜色差距变大diff加1或者减少1\n",
    "            res = dfs(index + 1, num, diff - 1) + dfs(index + 1, num + balls[index], diff + 1)\n",
    "            for i in range(1, balls[index]):\n",
    "                res += dfs(index + 1, num + i, diff) * comb(balls[index], i)\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans / comb(s, half)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def comb(x, y):\n",
    "            return int(math.factorial(x) / math.factorial(y) / math.factorial(x-y))\n",
    "\n",
    "        s = sum(balls)\n",
    "        l = len(balls)\n",
    "        # @lru_cache(None)\n",
    "        def dfs(curr, count, diff):\n",
    "            if curr == l:\n",
    "                return int(diff == 0 and count == s // 2)\n",
    "            res = dfs(curr+1, count, diff+1) + dfs(curr+1, count+balls[curr], diff-1)\n",
    "            for i in range(1, balls[curr]):\n",
    "                res += dfs(curr+1, count+i, diff) * comb(balls[curr], i)\n",
    "            return res\n",
    "        \n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / comb(s, s//2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "       self.colors = len(balls)\n",
    "       self.total = 0\n",
    "       self.res = 0\n",
    "       self.target_count = sum(balls) // 2\n",
    "       self.balls = balls\n",
    "       c1, c2 = 0, 0\n",
    "       self.dfs(c1, c2, 0, 0, 1)\n",
    "       return self.res / self.total\n",
    "\n",
    "\n",
    "    def dfs(self, c1: int, c2: int, count: int, idx: int, choice: int):\n",
    "        if count > self.target_count:\n",
    "            #选多了\n",
    "            return\n",
    "        if idx == self.colors: #颜色选完了\n",
    "            if count != self.target_count:\n",
    "                return\n",
    "            self.total += choice\n",
    "            if c1 == c2:\n",
    "                self.res += choice\n",
    "            return\n",
    "        # 当前颜色球有多少个\n",
    "        ball_count = self.balls[idx]\n",
    "        # 取出 i 个球放在第一个箱子，其余的放入第二个箱子\n",
    "        for i in range(ball_count + 1):\n",
    "            c11 = c1 + (0 if i == 0 else 1)\n",
    "            c22 = c2 + (0 if i == ball_count else 1)\n",
    "            this_choice = math.factorial(ball_count) / math.factorial(i) / math.factorial(ball_count - i) \n",
    "            self.dfs(c11, c22, count + i, idx + 1, choice * this_choice)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def getRes(lst):\n",
    "            res = 1\n",
    "            for x, y in zip(lst, balls):\n",
    "                res *= comb(y, x)\n",
    "            return res\n",
    "\n",
    "        ans = 0\n",
    "        tmp = 0\n",
    "\n",
    "        def dfs(idx, tmp1, tmp2):\n",
    "            nonlocal ans, tmp\n",
    "            if idx == len(balls):\n",
    "                if sum(tmp1) == sum(tmp2):\n",
    "                    methods = getRes(tmp1)\n",
    "                    if tmp1.count(0) == tmp2.count(0):\n",
    "                        ans += methods\n",
    "                    tmp += methods\n",
    "                return \n",
    "            for i in range(balls[idx]+1):\n",
    "                tmp1.append(i)\n",
    "                tmp2.append(balls[idx]-i)\n",
    "                dfs(idx+1, tmp1, tmp2)\n",
    "                tmp1.pop()\n",
    "                tmp2.pop()\n",
    "\n",
    "        dfs(0, [], [])\n",
    "        \n",
    "        return ans / tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        # def combine(x, y):#组合数\n",
    "            # return math.factorial(x) // math.factorial(y) // math.factorial(x - y)\n",
    "        s = sum(balls)#球总数\n",
    "        l = len(balls)#颜色总数\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c, t):\n",
    "            if i == l:#如果颜色选完了\n",
    "                return int(t == 0 and c == s // 2) #选了1/2的球数量且颜色无变化\n",
    "            res = dfs(i + 1, c, t - 1) + dfs(i + 1, c + balls[i], t + 1)#不选和全选组合数都为1，直接相加即可，需要更新颜色变化\n",
    "            for j in range(1, balls[i]):#其他情况，颜色无变化\n",
    "                res += dfs(i + 1, c + j, t) * comb(balls[i], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / comb(s, s // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def comb(x, y):\n",
    "            return int(math.factorial(x) / math.factorial(y) / math.factorial(x-y))\n",
    "\n",
    "        s = sum(balls)\n",
    "        l = len(balls)\n",
    "        @lru_cache(None)\n",
    "        def dfs(curr, count, diff):\n",
    "            if curr == l:\n",
    "                return int(diff == 0 and count == s // 2)\n",
    "            res = dfs(curr+1, count, diff+1) + dfs(curr+1, count+balls[curr], diff-1)\n",
    "            for i in range(1, balls[curr]):\n",
    "                res += dfs(curr+1, count+i, diff) * comb(balls[curr], i)\n",
    "            return res\n",
    "        \n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / comb(s, s//2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        s = sum(balls)\n",
    "        n = len(balls)\n",
    "        total,ss = 1,s\n",
    "        for i in balls:\n",
    "            total *= comb(ss,i)\n",
    "            ss -= i\n",
    "        @cache\n",
    "        def dfs(lft,rgt,lc,rc,pos):\n",
    "            if pos == n:return 1 if lc == rc else 0\n",
    "            l = min(lft,balls[pos]);r = max(balls[pos]-lft,0);shold = min(rgt,balls[pos])\n",
    "            res = 0\n",
    "            while r <= shold:\n",
    "                res += comb(lft,l) * comb(rgt,r) * dfs(lft-l,rgt-r,lc+(1 if not r else 0),rc+(1 if not l else 0),pos+1)\n",
    "                l-=1;r+=1\n",
    "            return res\n",
    "        return dfs(s//2,s//2,0,0,0)/total\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        n, s = len(balls), sum(balls)\n",
    "        half = s >> 1\n",
    "        # @cache\n",
    "        def dfs(index, num, diff):\n",
    "            if index == n:\n",
    "                return int(num == half and diff == 0)\n",
    "            # 这个颜色选择多少进入一个其中一个箱子\n",
    "            # 要么一个不选 要么全部选进其中一个箱子 这会导致颜色差距变大diff加1或者减少1\n",
    "            res = dfs(index + 1, num, diff - 1) + dfs(index + 1, num + balls[index], diff + 1)\n",
    "            for i in range(1, balls[index]):\n",
    "                res += dfs(index + 1, num + i, diff) * comb(balls[index], i)\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(0, 0, 0)\n",
    "        # dfs.cache_clear()\n",
    "        return ans / comb(s, half)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        n = sum(balls) // 2\n",
    "        m = len(balls)\n",
    "        mi_color = (m + 1) // 2\n",
    "        mx_color = m \n",
    "        ans = 0\n",
    "        perms = [1] * (2 * n + 1)\n",
    "        # for i in range(2, 2 * n + 1):\n",
    "        #     perms[i] = perms[i - 1] * i \n",
    "        \"\"\"\n",
    "        color: 颜色数限定值\n",
    "        layer: 来到第几关了（上限m）\n",
    "        L: 当前状态数组\n",
    "        rest_balls: 还能挑几个球？\n",
    "        rest_color: 还差几种颜色\n",
    "        \"\"\"\n",
    "\n",
    "        def g(L):\n",
    "            res = 1\n",
    "            for i in range(m):\n",
    "                if L[i]:\n",
    "                    res *= comb(balls[i], L[i])\n",
    "            return res \n",
    "\n",
    "        def judge(L, color):\n",
    "            tarn_L = [int((balls[i] - L[i]) > 0) for i in range(m)]\n",
    "            return sum(tarn_L) == color\n",
    "\n",
    "        def f(color, layer, L, rest_balls, rest_color):\n",
    "            nonlocal ans \n",
    "            if layer == m:\n",
    "                if rest_balls == 0 and rest_color == 0 and judge(L, color):\n",
    "                    ans += g(L)\n",
    "                    # ans += perms[n]\n",
    "                return \n",
    "            if rest_color == 0:\n",
    "                if rest_balls != 0:\n",
    "                    return \n",
    "                else:\n",
    "                    f(color, m, L + [0] * (m - layer), 0, 0)\n",
    "            else:\n",
    "                f(color, layer + 1, L + [0], rest_balls, rest_color)\n",
    "                for i in range(1, min(balls[layer], rest_balls) + 1):\n",
    "                    f(color, layer + 1, L + [i], rest_balls - i, rest_color - 1)\n",
    "        \n",
    "        for col in range(mi_color, mx_color + 1):\n",
    "            f(col, 0, [], n, col)\n",
    "        return ans / comb(2 * n, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def getRes(lst):\n",
    "            res = 1\n",
    "            for x, y in zip(lst, balls):\n",
    "                res *= comb(y, x)\n",
    "            return res\n",
    "        ans = 0\n",
    "        tmp = 0\n",
    "        def dfs(idx, tmp1, tmp2):\n",
    "            nonlocal ans, tmp\n",
    "            if idx == len(balls):\n",
    "                if sum(tmp1) == sum(tmp2):\n",
    "                    methods = getRes(tmp1)\n",
    "                    if tmp1.count(0) == tmp2.count(0):\n",
    "                        ans += methods\n",
    "                    tmp += methods\n",
    "                return \n",
    "            for i in range(balls[idx]+1):\n",
    "                tmp1.append(i)\n",
    "                tmp2.append(balls[idx]-i)\n",
    "                dfs(idx+1, tmp1, tmp2)\n",
    "                tmp1.pop()\n",
    "                tmp2.pop()\n",
    "        dfs(0, [], [])\n",
    "        return ans / tmp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 计算阶乘\n",
    "    def fact(self, n):\n",
    "        ans = 1\n",
    "        for i in range (1, n + 1):\n",
    "            ans *= i\n",
    "        return ans\n",
    "\n",
    "    # 计算可重复数排列\n",
    "    def get(self, balls):\n",
    "        tot = self.fact(sum(balls))\n",
    "        for b in balls:\n",
    "            if b:\n",
    "                tot /= self.fact(b)\n",
    "        return tot\n",
    "\n",
    "    # 暴搜每个颜色的所有可能\n",
    "    def dfs(self, u, balls, left, right, ts, ls, rs):\n",
    "        if ls * 2 > ts or rs * 2 > ts: return 0 # 不满足每个盒子放n个\n",
    "        # 所有颜色都选了\n",
    "        if u == len(balls):\n",
    "            # 统计左右颜色的个数\n",
    "            l = 0\n",
    "            r = 0\n",
    "            for x in left:\n",
    "                if x:\n",
    "                    l += 1\n",
    "            for x in right:\n",
    "                if x:\n",
    "                    r += 1\n",
    "            if l != r: return 0\n",
    "            # 对当前颜色方案计算可重复排列，比如1个color0 0个color1 2个color2，可以排列0 2 2, 2 0 2\n",
    "            return self.get(left) * self.get(right)\n",
    "        \n",
    "        # 暴搜当前balls[u]颜色，选0到balls[u]个\n",
    "        res = 0\n",
    "        for i in range(balls[u] + 1):\n",
    "            left[u] = i\n",
    "            right[u] = balls[u] - i\n",
    "            res += self.dfs(u + 1, balls, left, right, ts, ls + left[u], rs + right[u])\n",
    "        return res\n",
    "\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        l = [0 for i in range(len(balls))]\n",
    "        r = [0 for i in range(len(balls))]\n",
    "        return self.dfs(0, balls, l, r, sum(balls), 0, 0) / self.get(balls)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import comb\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        n = sum(balls) // 2\n",
    "        k = len(balls)\n",
    "        dp: list[dict[tuple[int, int, int], float]] = [dict(), dict()]\n",
    "        dp[0][0, 0, 0] = 1.0\n",
    "\n",
    "        for i, ball in enumerate(balls):\n",
    "            dp[i & 1 ^ 1].clear()\n",
    "            for (a, b, c), p in dp[i & 1].items():\n",
    "                ways = comb(2 * n - a - b, ball)\n",
    "                for ba in range(max(0, ball + b - n), min(ball, n - a) + 1):\n",
    "                    bb = ball - ba\n",
    "                    nxt_c = c + (1 if ba > 0 else 0) - (1 if bb > 0 else 0)\n",
    "                    if i - k + 1 <= nxt_c <= k - i - 1:\n",
    "                        nxt_a = a + ba\n",
    "                        nxt_b = b + bb\n",
    "                        dp[i & 1 ^ 1].setdefault((nxt_a, nxt_b, nxt_c), 0.0)\n",
    "                        dp[i & 1 ^ 1][nxt_a, nxt_b, nxt_c] += p * comb(n - a, ba) * comb(n - b, bb) / ways\n",
    "        \n",
    "        return sum(dp[k & 1].values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "    \n",
    "        s = sum(balls)#球总数\n",
    "        l = len(balls)#颜色总数\n",
    "        #@lru_cache(None)\n",
    "        def dfs(i, c, t):\n",
    "            if i == l:#如果颜色选完了\n",
    "                return int(t == 0 and c == s // 2) #选了1/2的球数量且颜色无变化\n",
    "            res = dfs(i + 1, c, t - 1) + dfs(i + 1, c + balls[i], t + 1)#不选和全选组合数都为1，直接相加即可，需要更新颜色变化\n",
    "            for j in range(1, balls[i]):#其他情况，颜色无变化\n",
    "                res += dfs(i + 1, c + j, t) * comb(balls[i], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / comb(s, s // 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def combine(x, y):#组合数\n",
    "            return math.factorial(x) // math.factorial(y) // math.factorial(x - y)\n",
    "        s = sum(balls)#球总数\n",
    "        l = len(balls)#颜色总数\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c, t):\n",
    "            if i == l:#如果颜色选完了\n",
    "                return int(t == 0 and c == s // 2) #选了1/2的球数量且颜色无变化\n",
    "            res = dfs(i + 1, c, t + 1) + dfs(i + 1, c + balls[i], t - 1)#不选和全选组合数都为1，直接相加即可，需要更新颜色变化\n",
    "            for j in range(1, balls[i]):#其他情况，颜色无变化\n",
    "                res += dfs(i + 1, c + j, t) * combine(balls[i], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / combine(s, s // 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def combine(x, y):#组合数\n",
    "            return math.factorial(x) // math.factorial(y) // math.factorial(x - y)\n",
    "        s = sum(balls)#球总数\n",
    "        l = len(balls)#颜色总数\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c, t):\n",
    "            if i == l:#如果颜色选完了\n",
    "                return int(t == 0 and c == s // 2) #选了1/2的球数量且颜色无变化\n",
    "            res = dfs(i + 1, c, t + 1) + dfs(i + 1, c + balls[i], t - 1)#不选和全选组合数都为1，直接相加即可，需要更新颜色变化\n",
    "            for j in range(1, balls[i]):#其他情况，颜色无变化\n",
    "                res += dfs(i + 1, c + j, t) * combine(balls[i], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / combine(s, s // 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def combine(x, y):\n",
    "            return math.factorial(x)//math.factorial(y)//math.factorial(x-y)\n",
    "        m=sum(balls)\n",
    "        n=len(balls)\n",
    "        @cache\n",
    "        def dfs(i,c,t):\n",
    "            if c>m//2:\n",
    "                return 0\n",
    "            if i==n:\n",
    "                return int(t==0 and c==m//2)\n",
    "            res = dfs(i+1,c,t+1)+dfs(i+1,c+balls[i],t-1)\n",
    "            for j in range(1,balls[i]):\n",
    "                res+=dfs(i+1,c+j,t)*combine(balls[i],j)\n",
    "            return res\n",
    "        res=dfs(0,0,0)\n",
    "        return res/combine(m,m//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "\n",
    "        m = len(balls)\n",
    "\n",
    "        n = sum(balls)\n",
    "\n",
    "        total = 1\n",
    "        rest = n\n",
    "        for num in balls:\n",
    "            total *= math.comb(rest, num)\n",
    "            rest -= num\n",
    "        pre = list(accumulate(balls, initial=0))\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, s, c1, c2):\n",
    "            if i == m:\n",
    "                return c1 == c2 and s == n//2\n",
    "            res = 0\n",
    "            t = pre[i] - s\n",
    "            for x in range(0, balls[i]+1):\n",
    "                if s + x <= n//2 and t + balls[i]-x <= n//2:\n",
    "                    res += dfs(i+1, s+x, c1+int(x>0), c2+int(x<balls[i]))*math.comb((n//2-s), x)*math.comb((n//2-t), balls[i]-x)\n",
    "\n",
    "            return res\n",
    "\n",
    "        return dfs(0, 0, 0, 0) / total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def getRes(lst):\n",
    "            res = 1\n",
    "            for x, y in zip(lst, balls):\n",
    "                res *= comb(y, x)\n",
    "            return res\n",
    "        ans = 0\n",
    "        tmp = 0\n",
    "        def dfs(idx, tmp1, tmp2):\n",
    "            nonlocal ans, tmp\n",
    "            if idx == len(balls):\n",
    "                if sum(tmp1) == sum(tmp2):\n",
    "                    methods = getRes(tmp1)\n",
    "                    if tmp1.count(0) == tmp2.count(0):\n",
    "                        ans += methods\n",
    "                    tmp += methods\n",
    "                return \n",
    "            for i in range(balls[idx]+1):\n",
    "                tmp1.append(i)\n",
    "                tmp2.append(balls[idx]-i)\n",
    "                dfs(idx+1, tmp1, tmp2)\n",
    "                tmp1.pop()\n",
    "                tmp2.pop()\n",
    "        dfs(0, [], [])\n",
    "        return ans / tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def combine(x, y):#组合数\n",
    "            return math.factorial(x) // math.factorial(y) // math.factorial(x - y)\n",
    "        s = sum(balls)#球总数\n",
    "        l = len(balls)#颜色总数\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c, t):\n",
    "            if i == l:#如果颜色选完了\n",
    "                return int(t == 0 and c == s // 2) #选了1/2的球数量且颜色无变化\n",
    "            res = dfs(i + 1, c, t + 1) + dfs(i + 1, c + balls[i], t - 1)#不选和全选组合数都为1，直接相加即可，需要更新颜色变化\n",
    "            for j in range(1, balls[i]):#其他情况，颜色无变化\n",
    "                res += dfs(i + 1, c + j, t) * combine(balls[i], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / combine(s, s // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def combine(x, y):#组合数\n",
    "            return math.factorial(x) // math.factorial(y) // math.factorial(x - y)\n",
    "        s = sum(balls)#球总数\n",
    "        l = len(balls)#颜色总数\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c, t):\n",
    "            if i == l:#如果颜色选完了\n",
    "                return int(t == 0 and c == s // 2) #选了1/2的球数量且颜色无变化\n",
    "            res = dfs(i + 1, c, t + 1) + dfs(i + 1, c + balls[i], t - 1)#不选和全选组合数都为1，直接相加即可，需要更新颜色变化\n",
    "            for j in range(1, balls[i]):#其他情况，颜色无变化\n",
    "                res += dfs(i + 1, c + j, t) * combine(balls[i], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / combine(s, s // 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        N = sum(balls) >> 1\n",
    "        n = len(balls)\n",
    "        path = []\n",
    "\n",
    "        # @cache\n",
    "        def cal(path: tuple[int]):\n",
    "            res = 1\n",
    "            left = N\n",
    "            for x in path:\n",
    "                if x == 0:\n",
    "                    continue\n",
    "                res *= comb(left, x)\n",
    "                left -= x\n",
    "            return res\n",
    "\n",
    "        # @cache\n",
    "        def dfs(i: int, diff: int, cnt: int, path: tuple[int]):\n",
    "            if cnt > N:\n",
    "                return 0\n",
    "            if i == n:\n",
    "                if cnt == N and diff == 0:\n",
    "                    # print(path)\n",
    "                    other = tuple([balls[i] - x for i, x in enumerate(path)])\n",
    "                    res = cal(path) * cal(other)\n",
    "                    return res\n",
    "                return 0\n",
    "            res = 0\n",
    "            for x in range(0, balls[i] + 1):\n",
    "                d = 0\n",
    "                if x == 0:\n",
    "                    d = -1\n",
    "                if x == balls[i]:\n",
    "                    d = 1\n",
    "                res += dfs(i + 1, diff + d, cnt + x, tuple(list(path) + [x]))\n",
    "            # print(i, diff, cnt, res)\n",
    "            return res\n",
    "\n",
    "        # @cache\n",
    "        def dfs2(i: int, left: int, right: int):\n",
    "            if i == n:\n",
    "                return left == 0 and right == 0\n",
    "            if left < 0 or right < 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for x in range(0, balls[i] + 1):\n",
    "                res += (\n",
    "                    comb(left, x)\n",
    "                    * comb(right, balls[i] - x)\n",
    "                    * dfs2(i + 1, left - x, right - (balls[i] - x))\n",
    "                )\n",
    "            return res\n",
    "\n",
    "        res = dfs(0, 0, 0, tuple(path))\n",
    "        # print(res)\n",
    "        res2 = dfs2(0, N, N)\n",
    "        # print(res2)\n",
    "        # dfs.cache_clear()\n",
    "        # dfs2.cache_clear()\n",
    "        return res / res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def combine(x, y):#组合数\n",
    "            return math.factorial(x) // math.factorial(y) // math.factorial(x - y)\n",
    "        s = sum(balls)#球总数\n",
    "        l = len(balls)#颜色总数\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c, t):\n",
    "            if i == l:#如果颜色选完了\n",
    "                return int(t == 0 and c == s // 2) #选了1/2的球数量且颜色无变化\n",
    "            res = dfs(i + 1, c, t + 1) + dfs(i + 1, c + balls[i], t - 1)#不选和全选组合数都为1，直接相加即可，需要更新颜色变化\n",
    "            for j in range(1, balls[i]):#其他情况，颜色无变化\n",
    "                res += dfs(i + 1, c + j, t) * combine(balls[i], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / combine(s, s // 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def combine(x, y):#组合数\n",
    "            return math.factorial(x) // math.factorial(y) // math.factorial(x - y)\n",
    "        s = sum(balls)#球总数\n",
    "        l = len(balls)#颜色总数\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c, t):\n",
    "            if i == l:#如果颜色选完了\n",
    "                return int(t == 0 and c == s // 2) #选了1/2的球数量且颜色无变化\n",
    "            res = dfs(i + 1, c, t + 1) + dfs(i + 1, c + balls[i], t - 1)#不选和全选组合数都为1，直接相加即可，需要更新颜色变化\n",
    "            for j in range(1, balls[i]):#其他情况，颜色无变化\n",
    "                res += dfs(i + 1, c + j, t) * combine(balls[i], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / combine(s, s // 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        ans = 0\n",
    "        k = len(balls)\n",
    "        n = sum(balls)\n",
    "\n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(n + 1):\n",
    "                if j:\n",
    "                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = 1\n",
    "        \n",
    "\n",
    "        def helper(p, a, b):\n",
    "            nonlocal ans\n",
    "            if p == k:\n",
    "                ac, bc, nums = 0, 0, [0, 0]\n",
    "                for i in range(k):\n",
    "                    if a[i]:\n",
    "                        ac += 1\n",
    "                        nums[0] += a[i]\n",
    "                    if b[i]:\n",
    "                        bc += 1\n",
    "                        nums[1] += b[i]\n",
    "\n",
    "                if ac == bc and nums[0] == nums[1]:\n",
    "                    res = 1\n",
    "                    for i in range(k):\n",
    "                        res *= dp[balls[i]][a[i]]\n",
    "                    ans += res / dp[n][nums[0]]\n",
    "                return\n",
    "            \n",
    "            for cnt in range(balls[p] + 1):\n",
    "                a[p] = cnt\n",
    "                b[p] = balls[p] - cnt\n",
    "                helper(p + 1, a, b)\n",
    "\n",
    "        helper(0, [0] * k, [0] * k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def combine(x, y):#组合数\n",
    "            return math.factorial(x) // math.factorial(y) // math.factorial(x - y)\n",
    "        s = sum(balls)#球总数\n",
    "        l = len(balls)#颜色总数\n",
    "        @cache\n",
    "        def dfs(i, c, t):\n",
    "            if i == l:#如果颜色选完了\n",
    "                return int(t == 0 and c == s // 2) #选了1/2的球数量且颜色无变化\n",
    "            res = dfs(i + 1, c, t + 1) + dfs(i + 1, c + balls[i], t - 1)#不选和全选组合数都为1，直接相加即可，需要更新颜色变化\n",
    "            for j in range(1, balls[i]):#其他情况，颜色无变化\n",
    "                res += dfs(i + 1, c + j, t) * combine(balls[i], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / combine(s, s // 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "    \n",
    "        s = sum(balls)#球总数\n",
    "        l = len(balls)#颜色总数\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c, t):\n",
    "            if i == l:#如果颜色选完了\n",
    "                return int(t == 0 and c == s // 2) #选了1/2的球数量且颜色无变化\n",
    "            res = dfs(i + 1, c, t + 1) + dfs(i + 1, c + balls[i], t - 1)#不选和全选组合数都为1，直接相加即可，需要更新颜色变化\n",
    "            for j in range(1, balls[i]):#其他情况，颜色无变化\n",
    "                res += dfs(i + 1, c + j, t) * comb(balls[i], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / comb(s, s // 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def comb(x, y):\n",
    "            return int(math.factorial(x) / math.factorial(y) / math.factorial(x-y))\n",
    "\n",
    "        s = sum(balls)\n",
    "        l = len(balls)\n",
    "        @lru_cache(None)\n",
    "        def dfs(curr, count, diff):\n",
    "            if curr == l:\n",
    "                return int(diff == 0 and count == s // 2)\n",
    "            res = dfs(curr+1, count, diff+1) + dfs(curr+1, count+balls[curr], diff-1)\n",
    "            for i in range(1, balls[curr]):\n",
    "                res += dfs(curr+1, count+i, diff) * comb(balls[curr], i)\n",
    "            return res\n",
    "        \n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / comb(s, s//2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "\n",
    "        n = len(balls)\n",
    "        s = sum(balls)\n",
    "        @cache\n",
    "        def dfs(idx, cnt, diff):\n",
    "            if idx == n:\n",
    "                return int(diff == 0 and cnt == s // 2)\n",
    "            \n",
    "            res = dfs(idx + 1, cnt, diff + 1) + dfs(idx + 1, cnt + balls[idx], diff - 1)\n",
    "\n",
    "            for j in range(1, balls[idx]):\n",
    "                res += dfs(idx + 1, cnt + j, diff) * comb(balls[idx], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / comb(s, s // 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        \n",
    "        s=sum(balls)\n",
    "        l=len(balls)\n",
    "        @cache\n",
    "        def dfs(i,c,t):\n",
    "            if i==l:\n",
    "                return c==s//2 and t==0\n",
    "            res=dfs(i+1,c,t+1)+dfs(i+1,c+balls[i],t-1)\n",
    "            for j in range(1,balls[i]):\n",
    "                res+=dfs(i+1,c+j,t)*comb(balls[i],j)\n",
    "            return res\n",
    "        res=dfs(0,0,0)\n",
    "        return res/comb(s,s//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def combine(x, y):\n",
    "            return math.factorial(x) // math.factorial(y) // math.factorial(x - y)\n",
    "        s = sum(balls)#球总数\n",
    "        l = len(balls)#颜色总数\n",
    "        @cache\n",
    "        def dfs(i, c, t):\n",
    "            if c>s//2:\n",
    "                return 0\n",
    "            if i == l:#如果颜色选完了\n",
    "                return int(t == 0 and c == s // 2) #选了1/2的球数量且颜色无变化\n",
    "            res = dfs(i + 1, c, t + 1) + dfs(i + 1, c + balls[i], t - 1)#不选和全选组合数都为1，直接相加即可，需要更新颜色变化\n",
    "            for j in range(1, balls[i]):#其他情况，颜色无变化\n",
    "                res += dfs(i + 1, c + j, t) * combine(balls[i], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / combine(s, s // 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        N = sum(balls) >> 1\n",
    "        n = len(balls)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, diff: int, cnt: int):\n",
    "            if cnt > N:\n",
    "                return 0\n",
    "            if i == n:\n",
    "                return cnt == N and diff == 0\n",
    "            res = 0\n",
    "            for x in range(0, balls[i] + 1):\n",
    "                d = 0\n",
    "                if x == 0:\n",
    "                    d = -1\n",
    "                if x == balls[i]:\n",
    "                    d = 1\n",
    "                res += comb(balls[i], x) * dfs(i + 1, diff + d, cnt + x)\n",
    "\n",
    "            return res\n",
    "\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / comb(2 * N, N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def comb(x,y):\n",
    "            return math.factorial(x)//math.factorial(y)//math.factorial(x-y)\n",
    "        s = sum(balls)\n",
    "        color_num = len(balls)\n",
    "        @lru_cache(None)\n",
    "        def dp(i, n, t):\n",
    "            '''第几个颜色，总数，分数'''\n",
    "            # 出口\n",
    "            if i == color_num:\n",
    "                return int(n==s//2 and t == 0)\n",
    "            \n",
    "            res = dp(i+1, n+balls[i], t+1) + dp(i+1, n, t-1)\n",
    "            for j in range(1,balls[i]):\n",
    "                res += dp(i+1,n + j, t ) * comb(balls[i],j)\n",
    "            return res \n",
    "        return dp(0,0,0)/comb(s,s//2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, diff: int) -> float:\n",
    "            if i >= k:\n",
    "                return 1 if j == 0 and diff == 0 else 0\n",
    "            if j < 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for x in range(balls[i] + 1):\n",
    "                y = 1 if x == balls[i] else (-1 if x == 0 else 0)\n",
    "                ans += dfs(i + 1, j - x, diff + y) * comb(balls[i], x)\n",
    "            return ans\n",
    "\n",
    "        n = sum(balls) >> 1\n",
    "        k = len(balls)\n",
    "        return dfs(0, n, 0) / comb(n << 1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        def combine(x, y):#组合数\n",
    "            return math.factorial(x) // math.factorial(y) // math.factorial(x - y)\n",
    "        s = sum(balls)#球总数\n",
    "        l = len(balls)#颜色总数\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c, t):\n",
    "            if i == l:#如果颜色选完了\n",
    "                return int(t == 0 and c == s // 2) #选了1/2的球数量且颜色无变化\n",
    "            res = dfs(i + 1, c, t - 1) + dfs(i + 1, c + balls[i], t + 1)#不选和全选组合数都为1，直接相加即可，需要更新颜色变化\n",
    "            for j in range(1, balls[i]):#其他情况，颜色无变化\n",
    "                res += dfs(i + 1, c + j, t) * combine(balls[i], j)\n",
    "            return res\n",
    "        res = dfs(0, 0, 0)\n",
    "        return res / combine(s, s // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        m = len(balls)  # m种颜色\n",
    "        cum_balls = [0]\n",
    "        for n in balls:\n",
    "            cum_balls.append(cum_balls[-1] + n)\n",
    "        s = cum_balls[-1] // 2  # s个球\n",
    "\n",
    "        # i个颜色，第一个里面有j分类，第二个里面有k颜色，第一个里面有n个球的种类数\n",
    "        data = [[[[0] * (s + 1) for _ in range(m + 1)] for _ in range(m + 1)] for _ in range(m + 1)]\n",
    "        all_data = [[0] * (s + 1) for _ in range(m + 1)]\n",
    "\n",
    "        data[0][0][0][0] = 1\n",
    "        all_data[0][0] = 1\n",
    "        for i in range(m):\n",
    "            for j in range(m + 1):\n",
    "                for k in range(m + 1):\n",
    "                    for n in range(s + 1):\n",
    "                        if data[i][j][k][n] == 0:\n",
    "                            continue\n",
    "\n",
    "                        if n + balls[i] <= s:\n",
    "                            data[i + 1][j + 1][k][n + balls[i]] += data[i][j][k][n]\n",
    "                        data[i + 1][j][k + 1][n] += data[i][j][k][n]\n",
    "\n",
    "                        for t in range(1, balls[i]):\n",
    "                            if n + t <= s:\n",
    "                                data[i + 1][j + 1][k + 1][n + t] += data[i][j][k][n] * self.select_cnt(balls[i], t)\n",
    "                            else:\n",
    "                                break\n",
    "\n",
    "            for n in range(s + 1):\n",
    "                if all_data[i][n] == 0:\n",
    "                    continue\n",
    "                for j in range(balls[i] + 1):\n",
    "                    if n + j <= s:\n",
    "                        all_data[i + 1][n + j] += all_data[i][n] * self.select_cnt(balls[i], j)\n",
    "\n",
    "        valid_cnt = 0\n",
    "        all_cnt = all_data[-1][s]\n",
    "        for j in range(m + 1):\n",
    "            valid_cnt += data[-1][j][j][s]\n",
    "\n",
    "        return valid_cnt / all_cnt\n",
    "    \n",
    "    @lru_cache()\n",
    "    def select_cnt(self, m, n):\n",
    "        p1 = 1\n",
    "        p2 = 1\n",
    "        for t in range(n):\n",
    "            p1 *= m - t\n",
    "            p2 *= n - t\n",
    "        return p1 / p2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        n = sum(balls) // 2\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, k, s1, s2):\n",
    "            if i == len(balls):\n",
    "                if s1 == s2 and k == n:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if k > n:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for j in range(balls[i] + 1):\n",
    "                if j == 0:\n",
    "                    res += dfs(i + 1, k + j, s1, s2 + 1) * comb(balls[i], j)\n",
    "                elif j == balls[i]:\n",
    "                    res += dfs(i + 1, k + j, s1 + 1, s2) * comb(balls[i], j)\n",
    "                else:\n",
    "                    res += dfs(i + 1, k + j, s1 + 1, s2 + 1) * comb(balls[i], j)\n",
    "            return res\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs2(i, k):\n",
    "            if i == len(balls):\n",
    "                if k == n:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if k > n:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for j in range(balls[i] + 1):\n",
    "                res += dfs2(i + 1, k + j) * comb(balls[i], j)\n",
    "            return res\n",
    "        return dfs(0, 0, 0, 0) / dfs2(0, 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    递归遍历\n",
    "    先要明白题意，题目就是要在2n个具有k种不同颜色的球中，随机抽取n个放入第一个盒子，剩下的n个放入第二个盒子，且两个盒子中不同颜色的个数相同的概率\n",
    "    在2n中选取n个的组合数为A，在n个球中选择m个放入盒子1，剩下的放入盒子2的组合数为B，我们只要判断盒子1和盒子2中颜色的种类相同，那么题目要求的总概率就是B/A，\n",
    "    而k种颜色中任何一种颜色往盒子1放多少，能正好满足两个盒子颜色种类相同的可能，根据乘法原则就是 B = b1 * b2 * b3 * ... * b3\n",
    "    '''\n",
    "    def getProbability(self, balls: List[int]) -> float:\n",
    "        ans = 0\n",
    "        k = len(balls)\n",
    "        '''\n",
    "        注意这里的n实际上就是题目中球的总数2n\n",
    "        '''\n",
    "        n = sum(balls)\n",
    "\n",
    "        '''\n",
    "        把组合数用递推的方式先算出来\n",
    "        dp[i][j]表示i个元素中取j个元素的组合数\n",
    "        '''\n",
    "        dp = [[0] * (2 * n + 1) for _ in range(2 * n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, 2 * n + 1):\n",
    "            for j in range(2 * n + 1):\n",
    "                if j:\n",
    "                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = 1\n",
    "        \n",
    "        '''\n",
    "        p：当前遍历到第几种颜色\n",
    "        a：第一个盒子中选择的颜色类型和对应的数量（数组）\n",
    "        b：第二个盒子中选择的颜色类型和对应的数量（数组）\n",
    "        '''\n",
    "        def helper(p, a, b):\n",
    "            nonlocal ans\n",
    "            '''\n",
    "            当分配到最后一种颜色，看看是否满足要求，如果满足要求就开始计算概率\n",
    "            '''\n",
    "            if p == k:\n",
    "                ac, bc, nums = 0, 0, [0, 0]\n",
    "                for i in range(k):\n",
    "                    if a[i]:\n",
    "                        ac += 1\n",
    "                        nums[0] += a[i]\n",
    "                    if b[i]:\n",
    "                        bc += 1\n",
    "                        nums[1] += b[i]\n",
    "                \n",
    "                if ac == bc and nums[0] == nums[1]:\n",
    "                    res = 1\n",
    "                    for i in range(k):\n",
    "                        '''\n",
    "                        既然当前的颜色和对应球的数量分配是合理的，那么就开始遍历计算每一种颜色分配的概率\n",
    "                        '''\n",
    "                        res *= dp[balls[i]][a[i]]\n",
    "                    '''\n",
    "                    把当前一种选择组合的概率算出来进行累加\n",
    "                    '''\n",
    "                    ans += res / dp[n][nums[0]]\n",
    "                return\n",
    "            '''\n",
    "            对应位置的颜色尝试任何一种分配方式，再递归选择下一个颜色继续分配\n",
    "            '''\n",
    "            for cnt in range(balls[p] + 1):\n",
    "                a[p] = cnt\n",
    "                b[p] = balls[p] - cnt\n",
    "                helper(p + 1, a, b)\n",
    "\n",
    "        helper(0, [0] * k, [0] * k)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
